class Solution {
public:
    int calculate(string s) {
        if (s.empty())
            return -1;
        int size = s.size();
        vector<int> values;
        vector<int> signs;
        int i = 0;
        while (i < size) {
            if (s[i] == ' ') {
                ++ i;
            } else if(s[i] == '+' || s[i] == '-') { // || s[i] == '-' || ) {
                if (signs.empty() && signs.back() != '(') {
                    int right = values.back();
                    values.pop_back();
                    int left = values.back();
                    values.pop_back();
                    if (signs.back() == '+')
                        values.push_back(left+right);
                    else
                        values.push_back(left-right);
                    signs.pop_back();
                } else // empty or top is '('
                    signs.push_back(s[i]);
                ++ i;
            } else if (s[i] >= '0' && s[i] <= '9') {
                string num;
                do {
                    num += s[i];
                    ++ i;
                } while(s[i] >= '0' && s[i] <= '9');
                values.push_back(stoi(num));
            } else if (s[i] == ')') {
                int right = values.back();
                values.pop_back();
                int left = values.back();
                values.pop_back();
                if (signs.back() == '+')
                    values.push_back(left+right);
                else
                    values.push_back(left-right);
                signs.pop_back(); // pop '+' or '-'
                signs.pop_back(); // pop '('
            } else {
                return -1;// invalid input
            }
        }
        // took
        return values.back();
    }
};